package com.zj.leetcode.medium.greed;

/**
 * @program: algorithm
 * @description:
 * 数组中的第K个最大元素
 * 215 kth-largest-element-in-an-array
 * @author: Zhang Bo
 * @create: 2022-03-30 12:23:00
 **/
public class KthLargestElementInAnArray{
    public static void main(String[] args) {
        Solution solution = new KthLargestElementInAnArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findKthLargest(int[] nums, int k) {
            this.heapSort(nums);
            int length = nums.length;
            return nums[length - k - 1];
        }

        //堆排序
        public void heapSort(int[] nums) {
            int len = nums.length;
            for (int i = len / 2 - 1; i >= 0; i--) {
                adjustHeap(nums, i, len);
            }

            while (len > 0) {
                swap(nums, 0, len - 1);
                len--;
                adjustHeap(nums, 0, len);
            }
        }

        private void adjustHeap(int[] nums, int i, int len) {
            int temp = nums[i];
            for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
                if (k + 1 < len && nums[k] > nums[k + 1]) {
                    k++;
                }

                if (nums[k] < temp) {
                    nums[i] = nums[k];
                    i = k;
                } else {
                    break;
                }
            }

            nums[i] = temp;
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
